package com.ljy.my_study.leetcode.省份数量;

import org.apache.commons.lang3.ArrayUtils;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

/**
 * @author lijunying
 * @date 2021/1/8 10:34
 */
public class TestMain {

//    有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
//
//    省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
//
//    给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
//
//    返回矩阵中 省份 的数量。
//
//             
//
//    示例 1：
//
//
//    输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
//    输出：2
//    示例 2：
//
//
//    输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
//    输出：3
//             
//
//    提示：
//
//            1 <= n <= 200
//    n == isConnected.length
//    n == isConnected[i].length
//    isConnected[i][j] 为 1 或 0
//    isConnected[i][i] == 1
//    isConnected[i][j] == isConnected[j][i]
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/number-of-provinces

    public static void main(String[] args) {
        TestMain testMain=new TestMain();
        int[][] isConnected={{1,0,0,0},{0,1,0,0},{0,0,0,1},{0,0,0,1}};
        System.out.println(testMain.findCircleNum(isConnected));
    }

    public int findCircleNum(int[][] isConnected) {
        int[] array=new int[isConnected.length];

        int num=1;
        for(int i=0;i<isConnected.length;i++){
            if(connect(isConnected,array,i,num)){
                num++;
            }
        }
        return num-1;
    }

//    1.关联
//    2.将两个关联的组合并
    private boolean connect(int[][] isConnected,int[] array,int index,int num){
        Set<Integer> set=new HashSet<>();
        for(int i=0;i<isConnected[index].length;i++){
            if(isConnected[index][i]==1){
                if(array[index]==0){
                    array[index]=num;
                }else if(array[index]!=num){
                    set.add(array[index]);
                }
                if(array[i]==0){
                    array[i]=num;
                    connect(isConnected,array,i,num);
                }else if(array[i]!=num){
                    set.add(array[i]);
                    connect(isConnected,array,i,array[index]);
                }
            }
        }
        if(!set.isEmpty()){
            set.add(num);
            changeConnect(array,set);
        }
        return set.isEmpty();
    }

    private void changeConnect(int[] array,Set<Integer> set){
        int min=Integer.MAX_VALUE;
        Iterator<Integer> it= set.iterator();
        while(it.hasNext()){
            min=Math.min(min,it.next());
        }
        for(int i=0;i<array.length;i++){
            array[i]=set.contains(array[i])?min:array[i];
        }
    }
}
